package TDAGrafo;

import TDALista.TElemento;
import TDALista.TLista;


/**
 * @author La revancha
 * @version 1.0
 */

public class TGrafoDirigido {

	public TLista vertices = new TLista();

	/**
	 * @param unaEtiqueta
	 * @return True si se pudo insertar el vertice, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean insertarVertice(Comparable unaEtiqueta) {
		if (existeVertice(unaEtiqueta)) {
			return false;
		}
		TVertice vert = new TVertice(unaEtiqueta);
		TElemento elem = new TElemento(unaEtiqueta, vert);
		vertices.insertarAlFinal(elem);
		return true;
	}

	/**
	 *
	 * @param unaEtiqueta
	 * @return el vertice indentificado por la etiqueta "unaEtiqueta"
	 */
	@SuppressWarnings("rawtypes")
	public TVertice buscarVertice(Comparable unaEtiqueta) {
		TElemento elem = vertices.buscarEtiqueta(unaEtiqueta);
		if (elem != null) {
			return (TVertice) elem.datos;
		}
		return null;
	}

	/**
	 * @param unaEtiqueta
	 * @return True si existe el vertice con la etiqueta indicada, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean existeVertice(Comparable unaEtiqueta) {
		return (buscarVertice(unaEtiqueta) != null);
	}

	/**
	 * @param etiquetaOrigen
	 * @param etiquetaDestino
	 * @param costo
	 * @return True si se pudo insertar la adyacencia, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean insertarAdyacencia(Comparable etiquetaOrigen, Comparable etiquetaDestino, Comparable costo) {

		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen != null) {
			TVertice destino = buscarVertice(etiquetaDestino);
			if (destino == null) {
				return false;
			}

			TAdyacencia nueva = new TAdyacencia(destino, costo);



			return origen.insertarAdyacencia(nueva);


		}
		return false;
	}

	/**
	 * @param etiquetaOrigen
	 * @param etiquetaDestino
	 * @return True si existe la adyacencia, false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean existeAdyacencia(Comparable etiquetaOrigen, Comparable etiquetaDestino) {

		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen != null) {
			for (TElemento actual = origen.adyacentes.primero; actual != null; actual = actual.siguiente) {
				if (((TAdyacencia) actual.datos).destino.etiqueta.equals(etiquetaDestino)) {
					return true;
				}
			}

			return false;
		}




		return false;

	}

	public void indicesVertices() {
		TVertice aux;
		int idx = 0;
		TElemento actual = vertices.primero;
		while (actual != null) {
			aux = (TVertice) actual.datos;
			aux.pos=idx;
			idx++;
			actual = actual.siguiente;
		}
	}
	// Retorna un array con los costos minimos

	@SuppressWarnings("rawtypes")
	public int[] dijkstra(Comparable etiquetaOrigen) {
		Integer[][] matriz = obtenerMatrizCostos();
		indicesVertices();
		int posicion = ((TVertice)(vertices.buscarEtiqueta(etiquetaOrigen).datos)).pos;
		return dijkstra(matriz, posicion);
		
	}

	public int[] dijkstra(Integer[][] matrizCostos, int posicion) {
		boolean sinProcesar[] = new boolean[matrizCostos.length];
		sinProcesar[0] = false;
		//maicol
		for (int i = 1; i < sinProcesar.length; i++) {
			sinProcesar[i] = true;
		}
		int caminoMinimos[] = new int[matrizCostos.length];
		caminoMinimos[posicion] = 0; // la distancia del origen al origen, es 0
		// Establecemos la distancia desde el vértice 0 a los demás vértices.
		for (int i = 1; i < caminoMinimos.length; i++) {
			if (matrizCostos[posicion][i] != null) {
				caminoMinimos[i] = matrizCostos[posicion][i];
			} else {
				caminoMinimos[i] = 0;
			}
		}
		int verticeSinCamino = 0;
		// Recorremos desde el primer vértice hasta el penúltimo.
		for (int i = 0; i < (sinProcesar.length - 2); i++) {
			// No tiene sentido calcular la distancia desde 0 hasta 0,
			// comenzamos en 1
			int contador = 1;
			// Buscamos el primer vértice al que no se le haya calculado el
			// camino mínimo
			while (!sinProcesar[contador]) {
				contador++;
			}
			verticeSinCamino = contador;
			// Comprobamos que el vértice elegido tenga la menor distancia al
			// origen.
			for (contador++; contador < sinProcesar.length; contador++) {
				/*
				 * Si el vértice está sin procesar Y la distancia al origen del
				 * vértice actual es mayor que la del nuevo entonces, pasamos a
				 * tratar el nuevo por estar a menor distancia.
				 */
				if (sinProcesar[contador] && caminoMinimos[verticeSinCamino] > caminoMinimos[contador]) {
					verticeSinCamino = contador;
				}
			}
			// El vértice ya está procesado!
			sinProcesar[verticeSinCamino] = false;
			// Actualizamos las distancias al origen comprobando las uniones que
			// tiene el vértice procesado.
			for (contador = 1; contador < sinProcesar.length; contador++) {
				/*
				 * Si el vértice no ha sido procesado Y la distancia actual al
				 * origen es mayor que la que habría pasando por el vértice
				 * recien procesado entonces, actualizamos la distancia mínima.
				 */
				if (matrizCostos[verticeSinCamino][contador] != null) {
					if (sinProcesar[contador] && (caminoMinimos[contador] > (caminoMinimos[verticeSinCamino] + matrizCostos[verticeSinCamino][contador]))) {
						caminoMinimos[contador] = caminoMinimos[verticeSinCamino] + matrizCostos[verticeSinCamino][contador];
					}
				}
			}
		}
		return caminoMinimos;
	}

	@SuppressWarnings("rawtypes")
	public Comparable[][] floyd() {
		int cantidadVertices = vertices.obtenerCantidadElementos();
		Integer[][] auxiliar = obtenerMatrizCostos();
		for (int k = 0; k < cantidadVertices; k++) {
			for (int i = 0; i < cantidadVertices; i++) {
				for (int j = 0; j < cantidadVertices; j++) {
					if ((i != k) && (k != j) && (i != j)) {
						if ((auxiliar[i][k] != null) && (auxiliar[k][j] != null)) {
							int costoIK = auxiliar[i][k].intValue();
							int costoKJ = auxiliar[k][j].intValue();
							int costoIJ = Integer.MAX_VALUE;
							if (auxiliar[i][j] != null) {
								costoIJ = auxiliar[i][j].intValue();
							}
							auxiliar[i][j] = Math.min(costoIJ, costoIK + costoKJ);
						}

					}

				}

			}

		}

		return auxiliar;


	}

	@SuppressWarnings("rawtypes")
	public int excentricidad(Comparable[][] matrizCostos, Comparable etiquetaOrigen) {
		if (!existeVertice(etiquetaOrigen)) {
			return -1;
		}
		Integer excentricidad = -1;
		int i = 0;
		for (TElemento aux = vertices.primero; !aux.etiqueta.equals(etiquetaOrigen); aux = aux.siguiente) {
			i++;
		}

		for (int s = 0; s < matrizCostos[0].length; s++) {
			if ((Integer) (matrizCostos[i][s]) != null) {
				if ((Integer) matrizCostos[i][s] > excentricidad) {
					excentricidad = (Integer) matrizCostos[i][s];
				}
			}
		}
		return excentricidad.intValue();

	}

	/**
	 * @return Etiqueta del centro del grafo
	 */
	@SuppressWarnings("rawtypes")
	public Comparable centroDelGrafo() {

		Comparable[][] matriz = floyd();
		int aux = Integer.MAX_VALUE;

		Comparable centro = null;
		for (TElemento vertice = vertices.primero; vertice != null; vertice = vertice.siguiente) {
			int excentricidad = excentricidad(matriz, vertice.etiqueta);
			if ((excentricidad != -1) && (excentricidad < aux)) {
				centro = vertice.etiqueta;
				aux = excentricidad;
			}
		}
		return centro;


	}

	public boolean[][] warshall() {

		int cantidadVertices = vertices.obtenerCantidadElementos();
		Integer[][] auxiliar = obtenerMatrizCostos();
		boolean[][] matrizb = new boolean[cantidadVertices][cantidadVertices];

		for (int s = 0; s < auxiliar.length; s++) {
			for (int h = 0; h < auxiliar.length; h++) {

				if ((auxiliar[s][h] != null) && (auxiliar[s][h] != Integer.MAX_VALUE)) {
					matrizb[s][h] = true;
				} else {
					matrizb[s][h] = false;
				}

			}

		}
		for (int k = 0; k < cantidadVertices; k++) {
			for (int i = 0; i < cantidadVertices; i++) {
				for (int j = 0; j < cantidadVertices; j++) {
					if (matrizb[i][j] == false) {
						matrizb[i][j] = matrizb[i][k] && matrizb[k][j];

					}

				}

			}

		}

		return matrizb;

	}

	public void desvisitar() {

		for (TElemento aux = vertices.primero; aux != null; aux = aux.siguiente) {

			TVertice actual = (TVertice) aux.datos;
			actual.visitado = false;
		}
	}

	@SuppressWarnings("rawtypes")
	public Comparable[] bpf(Comparable etiquetaOrigen) {

		TCamino camino = new TCamino();
		desvisitar();
		TVertice origen = buscarVertice(etiquetaOrigen);
		if (origen == null) {
			return null;
		}
		if (origen != null) {
			camino.origen = origen;
			origen.bpfinterno(camino);

		}

		return camino.mostrarCamino();
	}

	/**
	 *
	 * @param nombreVertice
	 * @return true si logro eliminar el vertice identificado por el Comparable "nombreVertice", false en caso contrario.
	 */
	@SuppressWarnings("rawtypes")
	public boolean eliminarVertice(Comparable nombreVertice) {

		boolean aretornar = vertices.eliminarEtiqueta(nombreVertice);
		TElemento aux = vertices.primero;

		while (aux != null) {
			TVertice aux2 = (TVertice) aux.datos;
			if (aux2.adyacentes.eliminarEtiqueta(nombreVertice)) {
				aretornar = true;
			}

			aux = aux.siguiente;
		}


		return aretornar;
	}

	/**
	 *
	 * @param nomVerticeOrigen
	 * @param nomVerticeDestino
	 * @return true si logro eliminar la adyacencia entre el vertice identificado por el Comparable "nombreVerticeOrigen"
	 * y el vertice "nombreVerticeDestino", false en caso contrario
	 */
	@SuppressWarnings("rawtypes")
	public boolean eliminarAdyacencia(Comparable nomVerticeOrigen, Comparable nomVerticeDestino) {
		TVertice origen = buscarVertice(nomVerticeOrigen);

		if (origen != null) {

			return (origen.adyacentes.eliminarEtiqueta(nomVerticeDestino));


		}
		return false;

	}

	/**
	 * @param etiquetaOrigen
	 * @param etiquetaDestino
	 * @param comparadorCaminos
	 * @return Un array con las claves de los vertices que componen el mejor camino, en caso de que exista
	 */
	@SuppressWarnings("rawtypes")
	public TCaminos todosLosCaminos(Comparable etiquetaOrigen, Comparable etiquetaDestino) {
		return null;
	}

	public TCaminos clasificacionTopologica() {
		return null;
	}

	public boolean tieneCiclos() {
		return false;
	}

	

	public Integer[][] obtenerMatrizCostos() {
		int cantidadVertices = vertices.obtenerCantidadElementos();
		Integer[][] matrizCostos = new Integer[cantidadVertices][cantidadVertices];
		int i = 0;
		TElemento elemVerticeI = vertices.primero;
		while (elemVerticeI != null) {
			int j = 0;
			TElemento elemVerticeJ = vertices.primero;
			while (elemVerticeJ != null) {
				if (!elemVerticeI.etiqueta.equals(elemVerticeJ.etiqueta)) {
					TVertice verticeI = (TVertice) elemVerticeI.datos;
					TVertice verticeJ = (TVertice) elemVerticeJ.datos;
					
					Integer costoAdyacencia = (Integer) verticeI.obtenerCostoAdyacencia(verticeJ);
					matrizCostos[i][j] = costoAdyacencia;
				}
				elemVerticeJ = elemVerticeJ.siguiente;
				j++;
			}
			elemVerticeI = elemVerticeI.siguiente;
			i++;
		}
		return matrizCostos;
	}
	
	@SuppressWarnings("rawtypes")
	public void imprimirMatriz(Integer[][] matriz, Comparable[] etiquetas) {
		System.out.print("  ");
		for(int i = 0;i < matriz.length; i++) {
			System.out.print(etiquetas[i] + "  ");
		}
		System.out.println();
		for(int i = 0;i < matriz.length; i++) {
			if (etiquetas[i]==null)
				System.out.print("-" + " ");
				else
			System.out.print(etiquetas[i] + " ");
			for(int j = 0; j < matriz.length; j++) {
				if (matriz[i][j]==null)
				System.out.print("-" + " ");
				else
					System.out.print(matriz[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	@SuppressWarnings("rawtypes")
	public String imprimirMatriz2(Comparable[][] matriz, Comparable[] etiquetas) {
		String aRetornar = "  ";
		for(int i = 0;i < matriz.length; i++) {
			aRetornar+= etiquetas[i] + "  ";
		}
		aRetornar+="\n";
		for(int i = 0;i < matriz.length; i++) {
			aRetornar+=etiquetas[i] + " ";
			for(int j = 0; j < matriz.length; j++) {
				aRetornar+=matriz[i][j] + " ";
			}
			aRetornar+="\n";
		}
		
		return aRetornar;
	}
}
